#include "binsearch.h"
using namespace std;

void Binsearch_and_insert(Elemtype A[], int &len, Elemtype x){
    int low, high, mid;
    low = 0;
    high = len-1;
    mid = (low + high) / 2;
    if (A[high] <= x ){
        A[len] = x;
        len++;
        return;
    }
    else if(A[low] >= x){
        NUO(A, len, -1);
        len++;
        A[0] = x;
        return;
    }
    while(low <= high){
        if(x > A[mid]){
            low = mid;
            mid = (low + high) / 2;
        }
        else if(x == A[mid]){
            NUO(A, len, mid);
            len++;
            A[mid] = x;
            return;
        }
        else if(x < A[mid]){
            high = mid;
            mid = (low + high) / 2;
        }
        if(high - low <= 1){
            NUO(A, len, low);
            len++;
            A[low+1] = x;
            return;
        }
    }
}

void NUO(Elemtype A[], int len, int start){
    int i;
    for(i = len; i > start; i--)
        A[i+1] = A[i];
    return ;
}
void Display(Elemtype A[], int len){
    int i;
    for(i = 0; i < len; i++){
        cout << A[i] << ' ' ;
    }
    cout << endl;
}
